#pragma once

#include <iostream>
#include <queue>
#include <algorithm>
#include <assert.h>
#include <vector>
#include <set>
#include "DesignExtractor.h"

using namespace std;

bool DesignExtractor::isExist = false;
DesignExtractor* DesignExtractor::de = NULL;

/*
Private constructor to uphold Singleton pattern
*/
DesignExtractor::DesignExtractor(PKB *origPKB) {
	//cout << "Creating DesignExractor..." << endl;
	pkb = origPKB;
	m_isBasicCompleted = false;
}

/*
Singleton pattern implentation
*/
DesignExtractor* DesignExtractor::getInstance() {
	/*if ( de == NULL) {
	de = new DesignExtractor;
	}*/
	return de;
}

/*
Run the DesignExtractor.
Error codes: 
0- No Error
1 - Error		
*/
int DesignExtractor::run() {
	//cout << "Extracting designs from PKB..." << endl;
	updateStarRelations();
	updateProcUMStatus();
	updateLineUMStatus();
	updateNextStatus();
	updateEarliestCommonParent();
	m_isBasicCompleted = true;
	//cout << "Done extracting designs from PKB!" << endl;
	return 0;
}

/*
Run the DesignExtractor to support extra features. Basic run() must be called first.
Error codes: 
0 - No Error
1 - Error		
*/
int DesignExtractor::runExtra() {
	if (!m_isBasicCompleted) {
		cout << "Error. Unable to execute runExtra() if basic run() of DesignExtractor has not been called yet.\n";
		return 1;
	}

	//cout << "Extracting designs from PKB to support extra features..." << endl;
	setExitPointsOfProcs();
	updateNextBipStatus();
	//updateNextBipStatus_YuDe();
	//cout << "Done extracting designs from PKB, extra features now supported!" << endl;
	return 0;
}


/*
Updates the PKB on uses/modifies status of each procedure
*/
int DesignExtractor::updateProcUMStatus() {
	//cout << "Updating uses/modifies status of each procedure..." << endl;
	// Initialize ADTs
	Type::List::Proc procListAll = pkb->getProcIndices();
	Type::List::Proc procListCallers;
	Type::List::Proc procListCallees;
	Type::List::Var varListAll = pkb->getVarIndices();
	Type::List::Var varListUsesNew;
	Type::List::Var varListUsesOld;
	Type::List::Var varListModsNew;
	Type::List::Var varListModsOld;
	Type::Index::Proc frontProcQueue;

	size_t numProcs = procListAll.size();
	size_t numVars = varListAll.size();
	vector<bool> isProcLeaf(numProcs + 1, false);
	vector<bool> isProcCompleted(numProcs + 1, false);
	queue<Type::Index::Proc> procQueue;
	bool tempResult = false;

	Type::Map::Bit procUsesBitmap(numProcs + 1, vector<bool>(numVars + 1, false));
	Type::Map::Bit procModsBitmap(numProcs + 1, vector<bool>(numVars + 1, false));

	// Maintain list of procs that do not call any other procs (leaves)
	for (size_t i = 0; i < procListAll.size(); i++) {
		if (pkb->getCalledBy(procListAll[i]).size() == 0){
			procQueue.push(procListAll[i]);
			isProcLeaf[procListAll[i]] = true;
		}
	}

	// Update Uses and Modifies relationships in queued order
	while (!procQueue.empty()) {

		frontProcQueue = procQueue.front();
		procQueue.pop();

		// Check if all callee procedures have been "completed"
		procListCallees = pkb->getCalledBy(frontProcQueue);
		if (!isCallersCompleted(frontProcQueue, isProcCompleted)) {
			procQueue.push(frontProcQueue);
			continue;
		}

		// Get the list of variables Used/Modified by callee procedures
		varListUsesOld.clear();
		varListModsOld.clear();

		// For every variable
		for (size_t varIndex = 0; varIndex < procUsesBitmap[0].size(); varIndex++) {
			// Check whether each callee procedure Uses that variable
			for (size_t procIndex = 0; procIndex < procListCallees.size(); procIndex++) {
				tempResult = tempResult || procUsesBitmap[procListCallees[procIndex]][varIndex];
			}
			// If even one of them does, add it to the list
			if (tempResult) {
				varListUsesOld.push_back(varIndex);
			}
			tempResult = false;
		}

		// For every variable
		for (size_t varIndex = 0; varIndex < procModsBitmap[0].size(); varIndex++) {
			// Check whether each callee procedure Modifies that variable
			for (size_t procIndex = 0; procIndex < procListCallees.size(); procIndex++) {
				tempResult = tempResult || procModsBitmap[procListCallees[procIndex]][varIndex];
			}
			// If even one of them does, add it to the list
			if (tempResult) {
				varListModsOld.push_back(varIndex);
			}
			tempResult = false;
		}

		// Add in any Uses and Modifies relationships found in lower level procs
		varListUsesNew = pkb->getUsedVarsByProc(frontProcQueue);
		varListUsesOld = vectorUnion(varListUsesOld, varListUsesNew);
		varListModsNew = pkb->getModifiedVarsByProc(frontProcQueue);
		varListModsOld = vectorUnion(varListModsOld, varListModsNew);

		// Update the pkb based on new information found
		for (size_t i = 0; i < varListUsesOld.size(); i++) {
			pkb->setProcUses(frontProcQueue, varListUsesOld[i]);
			procUsesBitmap[frontProcQueue][varListUsesOld[i]] = true;
		}
		for (size_t i = 0; i < varListModsOld.size(); i++) {
			pkb->setProcModifies(frontProcQueue, varListModsOld[i]);
			procModsBitmap[frontProcQueue][varListModsOld[i]] = true;
		}

		// Check procs that call current node
		procListCallers = pkb->getCallerOf(frontProcQueue);

		for (size_t i = 0; i < procListCallers.size(); i++) {
			procQueue.push(procListCallers[i]);
		}

		isProcCompleted[frontProcQueue] = true;

	}

	// Update pkb with bitmaps created
	assert(pkb->setProcUsesBitMap(procUsesBitmap));
	assert(pkb->setProcModifiesBitMap(procModsBitmap));

	return 0;
}

/*
Updates the PKB on uses/modifies status of each line
*/
int DesignExtractor::updateLineUMStatus() {
	//cout << "Updating PKB on uses/modifies status of each line..." << endl;
	// Initialize ADTs
	Type::List::Line lineListCalls = pkb->getLinesByEntity(Type::Entity::CALL_LINE_ENTITY);
	Type::List::Line lineListAll = pkb->getLines();
	Type::List::Line subCalleeProcList;
	Type::List::Var varListAll = pkb->getVarIndices();
	Type::List::Var varListUses;
	Type::List::Var varListMods;
	Type::List::Proc procListAll = pkb->getProcIndices();
	Type::Index::Proc calleeProc;
	Type::Index::Proc procOfCurrentLine;
	Type::Index::Line currentLine;

	size_t numLinesAll = lineListAll.size();
	size_t numVars = varListAll.size();

	Type::Map::Bit lineUsesBitmap(numLinesAll + 1, vector<bool>(numVars + 1, false));
	Type::Map::Bit lineModsBitmap(numLinesAll + 1, vector<bool>(numVars + 1, false)); 

	Type::Entity::Line lineType;
	queue<Type::Index::Line> lineQueueCalls;

	vector<bool> completedLinesCalls(numLinesAll + 1, false);
	vector<bool> completedProcs (pkb->getProcIndices().size() + 1, false);
	completedProcs.insert(completedProcs.begin(), 0);


	// Put all lines that have call statements into a queue
	for (size_t i = 0; i < lineListCalls.size(); i++) {
		lineQueueCalls.push(lineListCalls[i]);
	}

	// Set all procedures which do not call any other procedures 
	// to have "completed" the analysis. 
	for (size_t i = 0; i < procListAll.size(); i++) {
		if (pkb->getCalledBy(procListAll[i]).size() == 0){
			completedProcs[procListAll[i]] = true;
		}
	}

	// While the lineQueueCalls is not empty
	while (!lineQueueCalls.empty()) {	

		// Get the line at the front of the queue
		currentLine = lineQueueCalls.front();
		lineQueueCalls.pop();
		calleeProc = pkb->getCalledByLine(currentLine);
		subCalleeProcList = pkb->getCalledBy(calleeProc);

		// If the callee of the line itself calls another sub-procedure,
		// and that sub-procedure that it calls is not "completed",
		// put that line to the end of the queue and go to the next one.
		if (subCalleeProcList.size() != 0
			&& !isCompletedProc(subCalleeProcList, completedProcs)) {
				lineQueueCalls.push(currentLine);
				continue;
		}

		do{
			// Get entity type of line
			lineType = pkb->getLineEntityByLine(currentLine);

			// If it is a call statement, set callee proc and list of vars that are used/modified
			// Do not update varListUses and varListMods otherwise
			if (lineType == Type::Entity::CALL_LINE_ENTITY) {
				calleeProc = pkb->getCalledByLine(currentLine);
				varListUses = pkb->getUsedVarsByProc(calleeProc);
				varListMods = pkb->getModifiedVarsByProc(calleeProc);
				completedLinesCalls[currentLine] = true;
				procOfCurrentLine = pkb->getProcIndexOfLine(currentLine);

				if (isProcCompleted(procOfCurrentLine, completedLinesCalls)) {
					completedProcs[procOfCurrentLine] = true;
				}
			}

			varListUses = vectorUnion(varListUses, pkb->getUsedVarsByLine(currentLine));
			varListMods = vectorUnion(varListMods, pkb->getModifiedVarsByLine(currentLine));

			// Update pkb based on new information found
			for (size_t i = 0; i < varListUses.size(); i++) {
				pkb->setLineUses(currentLine, lineType, varListUses[i]);
				lineUsesBitmap[currentLine][varListUses[i]] = true;
			}

			for (size_t i = 0; i < varListMods.size(); i++) {
				pkb->setLineModifies(currentLine, lineType, varListMods[i]);
				lineModsBitmap[currentLine][varListMods[i]] = true;
			}

			// Go to the parent of the currentLine, if any
			currentLine = pkb->getParent(currentLine);

			// Repeat block if parent exists
		} while (currentLine != -1);

	}

	mergeBitmaps(lineUsesBitmap, lineModsBitmap);

	pkb->setLineUsesBitMap(lineUsesBitmap);
	pkb->setLineModifiesBitMap(lineModsBitmap);

	return 0;
}

/*
Updates the PKB on next status of each procedure
*/
int DesignExtractor::updateNextStatus() {
	//cout << "Updating Next relationships..." << endl;

	// Initialise ADTs
	Type::List::Proc procList = pkb->getProcIndices();
	Type::Pair::StartEnd startEnd;
	Type::Index::Line startLine;
	Type::List::Line childList;
	Type::List::Var varList = pkb->getVarIndices();

	size_t numLines = pkb->getLines().size();
	size_t numVars = varList.size();
	size_t numProcs = procList.size(); 
	Type::List::Line lmTableEntry(numVars + 1, 0);
	Type::List::Line nmTableEntry(numVars + 1, 0);

	m_isProcCompletedLastModified = vector<bool>(procList.size() + 1, false);
	m_isProcCompletedNextModified = vector<bool>(procList.size() + 1, false);
	m_confirmedVarsModifiedByProc = vector<vector<Type::Index::Var>>(numProcs + 1, vector<Type::Index::Var>(numVars + 1, 0));
	m_lastModifiedTable = Type::Map::LineMatrix(numLines + 1, vector<Type::Index::Line>(numVars + 1, 0));
	m_nextModifiedTable = Type::Map::LineMatrix(numLines + 1, vector<Type::Index::Line>(numVars + 1, 0));

	// Have to do individually for each procedure in the SIMPLE source
	for (size_t i = 0; i < numProcs; i++) {

		// Get the statementList of the procedure
		startEnd = pkb->getProcStartEnd(procList[i]);
		startLine = startEnd.first;
		childList = pkb->getFollowStar(startLine);
		childList.insert(childList.begin(), startLine);

		// Update Next relationships
		recurseAnalyseNext(childList);


		// Check if the proc has already been analysed for lastModified
		// (through Call statements during recursion)
		if (m_isProcCompletedLastModified[procList[i]] == true) {
			continue;
		}
		else {
			// Update lastModified table
			m_lastModifiedTable[childList[0]] = lmTableEntry;
			m_confirmedVarsModifiedByProc[procList[i]] = recurseAnalyseLastModified(true, childList, lmTableEntry);			
		}

		// Check if the proc has already been analysed for nextModified
		// (through Call statements during recursion)
		if (m_isProcCompletedNextModified[procList[i]] == true) {
			continue;
		}
		else {
			// Update nextModified table
			m_nextModifiedTable[childList[childList.size() - 1]] = nmTableEntry;
			recurseAnalyseNextModified(true, childList, nmTableEntry);
		}
	}

	pkb->setLastModified(m_lastModifiedTable);
	pkb->setNextModified(m_nextModifiedTable);
	//printLastNextTable(m_lastModifiedTable);
	//printLastNextTable(m_nextModifiedTable);

	return 0;
}
 
/*
Updates the PKB on nextBip status of each procedure
*/
int DesignExtractor::updateNextBipStatus() {
	//cout << "Updating NextBip relationships..." << endl;

	// Initialise ADTs
	Type::List::Proc procList = pkb->getProcIndices();
	Type::Pair::StartEnd startEnd;
	Type::Index::Line startLine;
	Type::List::Line childList;
	Type::List::Var varList = pkb->getVarIndices();
	Type::List::Line emptyList;

	size_t numLines = pkb->getLines().size();
	size_t numVars = varList.size();
	size_t numProcs = procList.size(); 

	// Have to do individually for each procedure in the SIMPLE source,
	// even though a procedure might have already been processed before 
	// from a CALL statement of another procedure. Must consider flow.
	for (size_t i = 0; i < numProcs; i++) {
		
		// Get the statementList of the procedure
		startEnd = pkb->getProcStartEnd(procList[i]);
		startLine = startEnd.first;
		childList = pkb->getFollowStar(startLine);
		childList.insert(childList.begin(), startLine);

		// Update NextBip relationships
		recurseAnalyseNextBip(childList, emptyList);
	}

	return 0;
}

/*
Recursive helper function to set the NextBip status of each childList
*/
int DesignExtractor::recurseAnalyseNextBip(Type::List::Line childList, Type::List::Line returnPoints) {
	// Initialise ADTs
	Type::Index::Line currentLine;
	Type::List::Line newChildList;
	Type::Entity::Line currentLineType;
	Type::Index::Line currentLineParent;		
	Type::List::Line emptyList;
	Type::Index::Proc currentProc;

	// Repeat for each child in the childList
	for (size_t i = 0; i < childList.size(); i++) {
		currentLine = childList[i];
		currentProc = pkb->getProcIndexOfLine(currentLine);
		currentLineType = pkb->getLineEntityByLine(currentLine);
		currentLineParent = pkb->getParent(currentLine);

		// If there exists a line in the same statement list 
		// after currentLine but does not follow it, 
		if ((i+1) < childList.size() &&
			!pkb->isFollows(currentLine, childList[i+1])) {
				// It means that two statements are separated by an else
				// and that parent must exist, and parent must be an if,	
				// so we set next(parent, secondLine) for the if` statement

				assert(currentLineParent == pkb->getParent(childList[i+1]));
				assert(pkb->getLineEntityByLine(currentLineParent) == Type::Entity::IF_LINE_ENTITY);
				pkb->setNextBip(currentLineParent, childList[i+1]);
		}

		// If the currentLine is a container statement,
		// set next(currentLine, first child of container statement)
		if (currentLineType == Type::Entity::WHILE_LINE_ENTITY || 
			currentLineType == Type::Entity::IF_LINE_ENTITY) {
				newChildList = pkb->getChild(currentLine);

				// Recurse within childList of container statement
				sort(newChildList.begin(), newChildList.end());
				pkb->setNextBip(currentLine, newChildList[0]);
				recurseAnalyseNextBip(newChildList, returnPoints);

				// If the currentLine is a while 
				if (currentLineType == Type::Entity::WHILE_LINE_ENTITY) {
					// If it has a following statement,
					// set next(currentLine, line following currentLine)
					if (pkb->getFollows(currentLine) != -1) {
						pkb->setNextBip(currentLine, childList[i+1]);
					}
					// If not, run the method to check for its parents' conditions
					else {
						checkParentConditions(currentLine);
					}
				}

		}
		// Else if it is an assignment statement
		// perform checks
		else if (currentLineType == Type::Entity::ASSIGNMENT_LINE_ENTITY) {
				// If there exists a line following the currentLine
				// in the same statement list,
				// there is no issue, just set next(currentLine, followingLine)
				if ((i+1) < childList.size() &&
					pkb->isFollows(currentLine, childList[i+1])) {
						pkb->setNextBip(currentLine, childList[i+1]);
						continue;
				}

				// **Reached only if currentLine has no following statement in childList**

				// Check the parents' conditions of the currentLine
				checkParentConditions(currentLine);
		}
		// Else if it is a call statement
		else if (currentLineType == Type::Entity::CALL_LINE_ENTITY) {
			// Get the statementList of the calleeProc
			Type::Index::Proc calleeProc = pkb->getCalledByLine(currentLine);
			Type::Index::Line firstLine = pkb->getProcStartEnd(calleeProc).first;
			newChildList = pkb->getFollowStar(firstLine);
			newChildList.insert(newChildList.begin(), firstLine);
			sort(newChildList.begin(), newChildList.end());

			// Set nextBip(currentLine, first line of callee proc)
			pkb->setNextBip(currentLine, firstLine);

		

			// Check if the CALL statement has a next, 
			// must make sure calleeProc sets nextBip to correct returnPoints
			// (set to self's returnPoints if next exists, else do not change,
			// set to callerProc's returnPoints) and then recurse.
			if (pkb->getSuccessorNext(currentLine).size() > 0) {
				Type::List::Line newReturnPoints = pkb->getSuccessorNext(currentLine);
				recurseAnalyseNextBip(newChildList, newReturnPoints);
			}
			else {
				recurseAnalyseNextBip(newChildList, returnPoints);	
			}
		}
		else {
			assert(false);
		}
	}

	// Set nextBip for endpoints of this procedure to the appropriate returnPoints, if any
	Type::List::Line endPoints = pkb->getProcExitPoints(currentProc);
	for (size_t rpIdx = 0; rpIdx < returnPoints.size(); rpIdx++) {
		for (size_t epIdx = 0; epIdx < endPoints.size(); epIdx++) {
			if (pkb->getLineEntityByLine(endPoints[epIdx]) != Type::Entity::CALL_LINE_ENTITY) {
				pkb->setNextBip(endPoints[epIdx], returnPoints[rpIdx]);
			}
		}
	}

	return 0;
}

/*
Helper function to check parent conditions for NextBip
*/
void DesignExtractor::checkParentConditionsBip(Type::Index::Line currentLine, Type::List::Line returnPoints) {
	Type::Index::Line currentLineParent = pkb->getParent(currentLine);
	Type::List::Line parentStarList;
	Type::Index::Line parent;

	// If currentLine has a parent
	if (currentLineParent != -1) {
		// If the parent is a while statement,
		// set nextBip(currentLine, parent)
		if (pkb->getLineEntityByLine(currentLineParent) == Type::Entity::WHILE_LINE_ENTITY) {
			pkb->setNextBip(currentLine, currentLineParent);
		}
		// Else if the parent is an if statement,
		else if (pkb->getLineEntityByLine(currentLineParent) == Type::Entity::IF_LINE_ENTITY) {
			// Must check if there is a while parent somewhere containing currentLine				
			// Also check if there is an if parent somewhere containint currentLine with a follows
			// Compare the two and check which is the deepest
			// and set the Next relationship accordingly
			parentStarList = pkb->getParentStar(currentLine);
			sort(parentStarList.begin(), parentStarList.end());
			for (size_t i = parentStarList.size() - 1; i >= 0; i--) {
				parent = parentStarList[i];
				if (pkb->getLineEntityByLine(parent) == Type::Entity::WHILE_LINE_ENTITY) {
					pkb->setNextBip(currentLine, parent);
					break;
				} 
				else if (pkb->getLineEntityByLine(parent) == Type::Entity::IF_LINE_ENTITY
					&& pkb->getFollows(parent) != -1 ) {
						pkb->setNextBip(currentLine, pkb->getFollows(parent));
						break;
				}

				if (i <= 0) {
					break;
				}
			} // endfor
		}
		else {
			assert(false);
		}
	}
}

/*
Updates all the Star relations in the PKB and store them for faster retrieval.
*/
int DesignExtractor::updateStarRelations() {
	//cout << "Updating Parent*/Follows*/Calls* relationships..." << endl;
	// Initialise ADTs
	Type::List::Line allLines = pkb->getLines();
	Type::List::Proc allProcs = pkb->getProcIndices();

	size_t numLines = allLines.size();
	size_t numProcs = allProcs.size();

	Type::Map::Bit followStarBitmap(numLines + 1, vector<bool>(numLines + 1, false));
	Type::Map::Bit parentStarBitmap(numLines + 1, vector<bool>(numLines + 1, false));
	Type::Map::Bit callsStarBitmap(numProcs + 1, vector<bool>(numProcs + 1, false));

	for (size_t i = 0; i < numLines; i++) {
		for (size_t j = 0; j < numLines; j++) {
			if (pkb->isFollowStar(allLines[i], allLines[j])) {
				followStarBitmap[allLines[i]][allLines[j]] = true;
			}
			if (pkb->isParentStar(allLines[i], allLines[j])) {
				parentStarBitmap[allLines[i]][allLines[j]] = true;
			}
		}
	}

	for (size_t i = 0; i < numProcs; i++) {
		for (size_t j = 0; j < numProcs; j++) {
			if (pkb->isCallsStar(allProcs[i], allProcs[j])) {
				callsStarBitmap[allProcs[i]][allProcs[j]] = true;
			}
		}
	}

	// ***Call the set functions here***
	pkb->setFollowStarBitMap(followStarBitmap);
	pkb->setParentStarBitMap(parentStarBitmap);
	pkb->setCallStarBitMap(callsStarBitmap);

	return 0;
}

/*
Creates and sets the lastModified table within the PKB in preparation for Affects
*/
Type::List::Var DesignExtractor::recurseAnalyseLastModified(bool isProc,
	Type::List::Line childList, Type::List::Line lmTableEntry) {	

		// Initialize ADTs
		Type::Index::Line currentLine;
		Type::Index::Line currentLineParent;
		Type::Entity::Line currentLineType;
		Type::List::Var modifiedVarsOfLine;
		Type::List::Var modifiedVarsOfBlock;
		Type::List::Line newChildList;
		Type::List::Var varList = pkb->getVarIndices();

		int numChildren = childList.size();
		int numVars = varList.size();

		// Check through all lines for lastModified
		for (size_t i = 0; i < childList.size(); i++) {
			currentLine = childList[i];
			currentLineParent = pkb->getParent(currentLine);
			currentLineType = pkb->getLineEntityByLine(currentLine);

			// If currentLine is an ASSINGMENT statement
			if (currentLineType == Type::Entity::ASSIGNMENT_LINE_ENTITY) {
				// Get modified vars of this line
				// and the lmTableEntry to be written.
				modifiedVarsOfLine = pkb->getModifiedVarsByLine(currentLine);
				lmTableEntry = updateTableEntry(currentLine, lmTableEntry, modifiedVarsOfLine);
			}
			// Else if it is a CALL statement
			else if (currentLineType == Type::Entity::CALL_LINE_ENTITY) {
				Type::Index::Proc calleeProc = pkb->getCalledByLine(currentLine);

				/* -|THIS PART WAS DEEMED REDUNDANT|-				
				cout << "calleeProcIndex: " << calleeProc << endl;
				// Check if calleeProc has been completed
				if (m_isProcCompletedLastModified[calleeProc]) {
					cout << "calleeProc HAS been processed before\n";
					// Set modifiedVarsOfLine to be that of previously calced value
					modifiedVarsOfLine = m_confirmedVarsModifiedByProc[calleeProc];
					cout << "CURRENTLINE: " << currentLine << endl;
					cout << "MODIFIEDVARSOFLINESIZE: " << modifiedVarsOfLine.size() << endl;
				}
				else {
					cout << "calleeProc has NOT been processed before.\n";
					// Get the statementList of the calleeProc
					Type::Index::Line startOfCalleeProc = pkb->getProcStartEnd(calleeProc).first;
					newChildList = pkb->getFollowStar(startOfCalleeProc);
					newChildList.insert(newChildList.begin(), startOfCalleeProc);
					sort(newChildList.begin(), newChildList.end());

					cout << "Setting table entry of first line of proc.\n";
					// Set the table entry of the first line to be zero
					Type::List::Var emptyTableEntry = Type::List::Line(numVars + 1, 0);
					m_lastModifiedTable[newChildList[0]] = emptyTableEntry;

					// Recurse within the callee procedure to get modifiedVarsOfLine
					// and the lmTableEntry to be written
					modifiedVarsOfLine = recurseAnalyseLastModified(true, newChildList, emptyTableEntry);	
				}
				*/

				// Get modified vars of the proc
				modifiedVarsOfLine = pkb->getModifiedVarsByProc(calleeProc);

				lmTableEntry = updateTableEntry(currentLine, lmTableEntry, modifiedVarsOfLine);

			}
			// Else if the currentLine is a WHILE statement
			else if (currentLineType == Type::Entity::WHILE_LINE_ENTITY) {
				// Get childList of currentLine
				newChildList = pkb->getChild(currentLine);
				sort(newChildList.begin(), newChildList.end());
				assert(newChildList[0] == currentLine + 1);

				m_lastModifiedTable[currentLine + 1] = lmTableEntry;
				recurseAnalyseLastModified(false, newChildList, lmTableEntry);

				//// Insert chidlList of the WHILE container into the current childList
				//childList = vectorUnion(childList, newChildList);
				//assert(currentLine = childList[i]);
			}
			// Else if the currentLine is an IF statement
			else if (currentLineType == Type::Entity::IF_LINE_ENTITY) {
				// Initialize some more variables
				Type::List::Line thenBlock;
				Type::List::Line elseBlock;
				Type::List::Var thenModifiedVars;
				Type::List::Var elseModifiedVars;
				bool isThenBlock = true;

				// Separate the THEN and ELSE blocks of the IF statement
				newChildList = pkb->getChild(currentLine);
				sort(newChildList.begin(), newChildList.end());
				for (size_t i = 0; i < newChildList.size(); i++)
				{
					if (isThenBlock) {
						thenBlock.push_back(newChildList[i]);
					}
					else {
						elseBlock.push_back(newChildList[i]);
					}
					if (i+1 < newChildList.size() &&
						!pkb->isFollows(newChildList[i], newChildList[i+1])) {
							assert(isThenBlock);
							isThenBlock = false;
					}
				}

				// Do not update tableEntry yet
				// Set first statement in each block to have the same lmTableEntry as currentLine
				m_lastModifiedTable[thenBlock[0]] = lmTableEntry;
				m_lastModifiedTable[elseBlock[0]] = lmTableEntry;

				// Recurse within each block
				// and get the modified vars of each block
				thenModifiedVars = recurseAnalyseLastModified(false, thenBlock, lmTableEntry);
				elseModifiedVars = recurseAnalyseLastModified(false, elseBlock, lmTableEntry);

				// Intersect the vectors to get the CONFIRMED modified vars of the whole IF block
				// and set the lmTableEntry to be written.
				modifiedVarsOfLine = vectorIntersect(thenModifiedVars, elseModifiedVars);
				lmTableEntry = updateTableEntry(currentLine, lmTableEntry, modifiedVarsOfLine);

			}
			else {
				assert(false);
			}

			// If there exists a line following the currentLine
			// in the same statement list, set the tableEntries
			if (i+1 < childList.size() && 
				(pkb->isFollows(currentLine, childList[i+1]) || 
				pkb->getLineEntityByLine(currentLine) == Type::Entity::WHILE_LINE_ENTITY || 
				pkb->getLineEntityByLine(currentLineParent) == Type::Entity::WHILE_LINE_ENTITY)) {
					m_lastModifiedTable[childList[i+1]] = lmTableEntry;
			}

			// Update modifiedVarsOfBlock
			modifiedVarsOfBlock = vectorUnion(modifiedVarsOfBlock, modifiedVarsOfLine);
		}

		// If this block was a whole procedure, set it as done.
		if (isProc) {
			Type::Index::Proc currentProc = pkb->getProcIndexOfLine(childList[0]);
			m_confirmedVarsModifiedByProc[currentProc] = modifiedVarsOfBlock;
			m_isProcCompletedLastModified[currentProc] = true;
		}

		return modifiedVarsOfBlock;
}

/*
Creates and sets the nextModified table within the PKB in preparation for Affects
*/
Type::List::Var DesignExtractor::recurseAnalyseNextModified(bool isProc,
	Type::List::Line childList, Type::List::Line nmTableEntry) {	

		// Initialize ADTs
		Type::Index::Line currentLine;
		Type::Index::Line currentLineParent;
		Type::Entity::Line currentLineType;
		Type::List::Var modifiedVarsOfLine;
		Type::List::Var modifiedVarsOfBlock;
		Type::List::Line newChildList;
		Type::List::Var varList = pkb->getVarIndices();
		vector<bool> completedWhileList(pkb->getLines().size(), false);

		int numChildren = childList.size();
		int numVars = varList.size();

		// Check through all lines for nextModified
		for (size_t i = childList.size() - 1; i >= 0; i--) {
			currentLine = childList[i];
			currentLineParent = pkb->getParent(currentLine);
			currentLineType = pkb->getLineEntityByLine(currentLine);

			m_nextModifiedTable[currentLine] = nmTableEntry;

			// If currentLine is an ASSINGMENT statement
			if (currentLineType == Type::Entity::ASSIGNMENT_LINE_ENTITY) {
				// Get modified vars of this line
				// and the lmTableEntry to be written.
				modifiedVarsOfLine = pkb->getModifiedVarsByLine(currentLine);
				nmTableEntry = updateTableEntry(currentLine, nmTableEntry, modifiedVarsOfLine);
			}
			// Else if it is a CALL statement
			else if (currentLineType == Type::Entity::CALL_LINE_ENTITY) {
				Type::Index::Proc calleeProc = pkb->getCalledByLine(currentLine);

				/* -|THIS PART WAS DEEMED REDUNDANT|-	
				cout << "calleeProcIndex: " << calleeProc << endl;
				// Check if calleeProc has been completed
				if (m_isProcCompletedNextModified[calleeProc]) {
					cout << "calleeProc HAS been processed before\n";
					// Set modifiedVarsOfLine to be that of previously calced value
					modifiedVarsOfLine = m_confirmedVarsModifiedByProc[calleeProc];
					cout << "CURRENTLINE: " << currentLine << endl;
					cout << "MODIFIEDVARSOFLINESIZE: " << modifiedVarsOfLine.size() << endl;
				}
				else {
					cout << "calleeProc has NOT been processed before.\n";
					// Get the statementList of the calleeProc
					Type::Index::Line startOfCalleeProc = pkb->getProcStartEnd(calleeProc).first;
					newChildList = pkb->getFollowStar(startOfCalleeProc);
					newChildList.insert(newChildList.begin(), startOfCalleeProc);
					sort(newChildList.begin(), newChildList.end());

					cout << "Setting table entry of last line of proc.\n";
					// Set the table entry of the last line to be zero
					Type::List::Var emptyTableEntry = Type::List::Line(numVars + 1, 0);
					m_nextModifiedTable[newChildList[newChildList.size() - 1]] = emptyTableEntry;

					// Recurse within the callee procedure to get modifiedVarsOfLine
					// and the nmTableEntry to be written
					modifiedVarsOfLine = recurseAnalyseNextModified(true, newChildList, emptyTableEntry);
				}
				*/

				// Get modified vars of the callee proc
				modifiedVarsOfLine = pkb->getModifiedVarsByProc(calleeProc);

				nmTableEntry = updateTableEntry(currentLine, nmTableEntry, modifiedVarsOfLine);
			}
			// Else if the currentLine is a WHILE statement
			else if (currentLineType == Type::Entity::WHILE_LINE_ENTITY) {

				// Check if this while has already been done
				if (!completedWhileList[currentLine]) {
					// Get childList of currentLine
					newChildList = pkb->getChild(currentLine);
					sort(newChildList.begin(), newChildList.end());
					assert(newChildList[0] == currentLine + 1);

					recurseAnalyseNextModified(false, newChildList, nmTableEntry);

					//// Insert chidlList of the WHILE container into the current childList
					//childList = vectorUnion(childList, newChildList);
					//i += newChildList.size() + 1;
					//assert(childList[i-1] == newChildList.back());

					//// Mark this while as done to prevent infinite loop
					//completedWhileList[currentLine] = true;

					//if (i < childList.size()) {
					//	currentLine = childList[i];
					//	currentLineParent = pkb->getParent(currentLine);
					//	currentLineType = pkb->getLineEntityByLine(currentLine);
					//}
				}
			}
			// Else if the currentLine is an IF statement
			else if (currentLineType == Type::Entity::IF_LINE_ENTITY) {

				// Initialize some more variables
				Type::List::Line thenBlock;
				Type::List::Line elseBlock;
				Type::List::Var thenModifiedVars;
				Type::List::Var elseModifiedVars;
				bool isThenBlock = true;

				// Separate the THEN and ELSE blocks of the IF statement
				newChildList = pkb->getChild(currentLine);
				sort(newChildList.begin(), newChildList.end());
				for (size_t i = 0; i < newChildList.size(); i++)
				{
					if (isThenBlock) {
						thenBlock.push_back(newChildList[i]);
					}
					else {
						elseBlock.push_back(newChildList[i]);
					}
					if (i+1 < newChildList.size() &&
						!pkb->isFollows(newChildList[i], newChildList[i+1])) {
							assert(isThenBlock);
							isThenBlock = false;
					}
				}

				// Do not update tableEntry yet
				// Set last statement in each block to have the same nmTableEntry as currentLine
				m_nextModifiedTable[thenBlock[thenBlock.size() - 1]] = nmTableEntry;
				m_nextModifiedTable[elseBlock[elseBlock.size() - 1]] = nmTableEntry;

				// Recurse within each block
				// and get the modified vars of each block
				thenModifiedVars = recurseAnalyseNextModified(false, thenBlock, nmTableEntry);
				elseModifiedVars = recurseAnalyseNextModified(false, elseBlock, nmTableEntry);

				// Intersect the vectors to get the CONFIRMED modified vars of the whole IF block
				// and set the lmTableEntry to be written.
				modifiedVarsOfLine = vectorIntersect(thenModifiedVars, elseModifiedVars);
				nmTableEntry = updateTableEntry(currentLine, nmTableEntry, modifiedVarsOfLine);

			}
			else {
				assert(false);
			}

			// Update modifiedVarsOfBlock
			modifiedVarsOfBlock = vectorUnion(modifiedVarsOfBlock, modifiedVarsOfLine);

			// If this block was a whole procedure, set it as done.
			if (isProc) {
				Type::Index::Proc currentProc = pkb->getProcIndexOfLine(childList[0]);
				m_isProcCompletedNextModified[currentProc] = true;
			}

			if (i <= 0) {
				break;
			}
		}

		return modifiedVarsOfBlock;
}

/*
Updates a tableEntry that with a list of modifiedVars
*/
Type::List::Line DesignExtractor::updateTableEntry(Type::Index::Line currentLine, Type::List::Line lmTableEntry, Type::List::Var modifiedVars) {	
	for (size_t i = 0; i < modifiedVars.size(); i++) {
		lmTableEntry[modifiedVars[i]] = currentLine;
	}

	return lmTableEntry;
}

/*
Recursive helper function to set the Next status of each childList
*/
int DesignExtractor::recurseAnalyseNext(Type::List::Line childList) {
	// Initialise ADTs
	Type::Index::Line currentLine;
	Type::List::Line newChildList;
	Type::Entity::Line currentLineType;
	Type::Index::Line currentLineParent;

	// Repeat for each child in the childList
	for (size_t i = 0; i < childList.size(); i++) {
		currentLine = childList[i];
		currentLineType = pkb->getLineEntityByLine(currentLine);
		currentLineParent = pkb->getParent(currentLine);

		// If there exists a line in the same statement list 
		// after currentLine but does not follow it, 
		if ((i+1) < childList.size() &&
			!pkb->isFollows(currentLine, childList[i+1])) {
				// It means that two statements are separated by an else
				// and that parent must exist, and parent must be an if,	
				// so we set next(parent, secondLine) for the if` statement

				assert(currentLineParent == pkb->getParent(childList[i+1]));
				assert(pkb->getLineEntityByLine(currentLineParent) == Type::Entity::IF_LINE_ENTITY);
				pkb->setNext(currentLineParent, childList[i+1]);
		}

		// If the currentLine is a container statement,
		// set next(currentLine, first child of container statement)
		if (currentLineType == Type::Entity::WHILE_LINE_ENTITY || 
			currentLineType == Type::Entity::IF_LINE_ENTITY) {
				newChildList = pkb->getChild(currentLine);

				// Recurse within childList of container statement
				sort(newChildList.begin(), newChildList.end());
				pkb->setNext(currentLine, newChildList[0]);
				recurseAnalyseNext(newChildList);

				// If the currentLine is a while 
				if (currentLineType == Type::Entity::WHILE_LINE_ENTITY) {
					// If it has a following statement,
					// set next(currentLine, line following currentLine)
					if (pkb->getFollows(currentLine) != -1) {
						pkb->setNext(currentLine, childList[i+1]);
					}
					// If not, run the method to check for its parents' conditions
					else {
						checkParentConditions(currentLine);
					}
				}

		}
		// Else if it is a normal statement(assign or call)
		// perform checks
		else if (currentLineType == Type::Entity::ASSIGNMENT_LINE_ENTITY ||
			currentLineType == Type::Entity::CALL_LINE_ENTITY) {
				// If there exists a line following the currentLine
				// in the same statement list,
				// there is no issue, just set next(currentLine, followingLine)
				if ((i+1) < childList.size() &&
					pkb->isFollows(currentLine, childList[i+1])) {
						pkb->setNext(currentLine, childList[i+1]);
						continue;
				}

				// **Reached only if currentLine has no following statement in childList**

				// Check the parents' conditions of the currentLine
				checkParentConditions(currentLine);
		}
		else {
			assert(false);
		}
	}
	return 0;
}

/*
Helper function to check parent conditions for Next
*/
void DesignExtractor::checkParentConditions(Type::Index::Line currentLine) {
	Type::Index::Line currentLineParent = pkb->getParent(currentLine);
	Type::List::Line parentStarList;
	Type::Index::Line parent;

	// If currentLine has a parent
	if (currentLineParent != -1) {
		// If the parent is a while statement,
		// set next(currentLine, parent)
		if (pkb->getLineEntityByLine(currentLineParent) == Type::Entity::WHILE_LINE_ENTITY) {
			pkb->setNext(currentLine, currentLineParent);
		}
		// Else if the parent is an if statement,
		else if (pkb->getLineEntityByLine(currentLineParent) == Type::Entity::IF_LINE_ENTITY) {
			// Must check if there is a while parent somewhere containing currentLine				
			// Also check if there is an if parent somewhere containint currentLine with a follows
			// Compare the two and check which is the deepest
			// and set the Next relationship accordingly
			parentStarList = pkb->getParentStar(currentLine);
			sort(parentStarList.begin(), parentStarList.end());
			for (size_t i = parentStarList.size() - 1; i >= 0; i--) {
				parent = parentStarList[i];
				if (pkb->getLineEntityByLine(parent) == Type::Entity::WHILE_LINE_ENTITY) {
					pkb->setNext(currentLine, parent);
					break;
				}
				else if (pkb->getLineEntityByLine(parent) == Type::Entity::IF_LINE_ENTITY
					&& pkb->getFollows(parent) != -1 ) {
						pkb->setNext(currentLine, pkb->getFollows(parent));
						break;
				}

				if (i == 0) {
					break;
				}
			}
		}
	}
}

/*
Helper function to union two vectors
*/
vector<int> DesignExtractor::vectorUnion(vector<int> first, vector<int> second) {
	vector<int> result(first.size() + second.size());
	vector<int>::iterator iter;
	sort(first.begin(), first.end());
	sort(second.begin(), second.end());
	iter = set_union(first.begin(), first.end(), second.begin(), second.end(), result.begin());
	result.resize(iter - result.begin());
	return result;
}

/*
Helper function to intersect two vectors
*/
vector<int> DesignExtractor::vectorIntersect(vector<int> first, vector<int> second) {
	vector<int> result(first.size() + second.size());
	vector<int>::iterator iter;
	sort(first.begin(), first.end());
	sort(second.begin(), second.end());
	iter = set_intersection(first.begin(), first.end(), second.begin(), second.end(), result.begin());
	result.resize(iter - result.begin());
	return result;
}

/*
Helper function to check if a proceure is "completed"
Checks if all sub-procedures called by this procedure have themselves been "completed"
*/
bool DesignExtractor::isCompletedProc(Type::List::Proc subCalleeProcList, vector<bool> completedProcs) {
	size_t count = 0;
	Type::Index::Proc currentProc;
	for (size_t i = 0; i < subCalleeProcList.size(); i++) {
		currentProc = subCalleeProcList[i];
		if (completedProcs[currentProc] == true) {
			count++;
		}
	}

	if (count == subCalleeProcList.size()) {
		return true;
	}
	else {
		return false;
	}
}

/*
Helper function to check whether all of a procedure's call statements have been analysed
*/
bool DesignExtractor::isProcCompleted(Type::Index::Proc proc, vector<bool> completedLinesCalls) {
	Type::List::Line allCallLines = pkb->getLinesByEntity(Type::Entity::CALL_LINE_ENTITY);
	Type::Pair::StartEnd startEnd = pkb->getProcStartEnd(proc);
	Type::Index::Line currentLine;

	for (size_t i = 0; i < allCallLines.size(); i++) {
		currentLine = allCallLines[i];
		if (startEnd.first <= currentLine && startEnd.second >= currentLine) {
			if (!completedLinesCalls[currentLine]) {
				return false;
			}
		}
	}

	return true;
}

/*
Helper function to check if callers of a procedure have been completed and processed.
*/
bool DesignExtractor::isCallersCompleted(Type::Index::Proc currentProc, vector<bool> isProcCompleted) {
	Type::List::Proc procListCallees = pkb->getCalledBy(currentProc);

	for (size_t i = 0; i < procListCallees.size(); i++) {
		if (!isProcCompleted[procListCallees[i]]) {
			return false;
		}
	}

	return true;
}

/*
Helper function to merge Uses/Modifies bitmaps computed in DE with the existing pkb info
*/
void DesignExtractor::mergeBitmaps(Type::Map::Bit &lineUsesBitmap, Type::Map::Bit &lineModsBitmap) {
	Type::List::Line lineList = pkb->getLines();
	Type::List::Line varList;
	Type::Index::Line currentLine;
	Type::Index::Var currentVar;

	for (size_t i = 0; i < lineList.size(); i++) {
		currentLine = lineList[i];
		varList = pkb->getUsedVarsByLine(currentLine);
		for (size_t j = 0; j < varList.size(); j++) {
			currentVar = varList[j];
			lineUsesBitmap[currentLine][currentVar] = true;
		}

		varList = pkb->getModifiedVarsByLine(lineList[i]);
		for (size_t j = 0; j < varList.size(); j++) {
			currentVar = varList[j];
			lineModsBitmap[currentLine][currentVar] = true;
		}
	}
}

/*
Utility function to member variable getLastModifiedTable 
*/
Type::Map::LineMatrix DesignExtractor::getLastModifiedTable() {
	return m_lastModifiedTable;
}

/*
Utility function to member variable getNextModifiedTable 
*/
Type::Map::LineMatrix DesignExtractor::getNextModifiedTable() {
	return m_nextModifiedTable;
}

/*
Utility method to print out lastModified and nextModified tables
*/
void DesignExtractor::printLastNextTable(vector<vector<int>> table) {
	cout << "----------------------------------------------------------" << endl;
	for (size_t j = 1; j < table[0].size(); j++) {
		cout << pkb->getVarName(j) << "\t";
	}
	cout << endl;
	for (size_t i = 1; i < table.size(); i++) {
		for (size_t j = 1; j < table[i].size(); j++) {
			cout << table[i][j] << "\t";
		}
		cout << "// " << i << endl;
	}
	cout << endl;
}

/// Method to update all Earliest Common Parent If and While
int DesignExtractor::updateEarliestCommonParent(){
	/// Method to update all Earliest Common While between two container statements
	updateEarliestCommonParent(Type::Entity::WHILE_LINE_ENTITY);
	/// Method to update all Earliest Common If between two container statements
	updateEarliestCommonParent(Type::Entity::IF_LINE_ENTITY);

	return 0;
}

/// Method to update all Earliest Common Parent between two container statements
void DesignExtractor::updateEarliestCommonParent(Type::Entity::Line containerEntity){
	Type::Map::ParentMatrix* parentMatrix = new Type::Map::ParentMatrix();

	Type::List::Line containerLines;
	Type::Index::Line startLine;
	Type::Index::Proc tmpProc;
	Type::Pair::StartEnd tmpPair;
	int earliest;

	Type::List::Proc procList = pkb->getProcIndices();
	for(unsigned int h=0; h<procList.size(); h++){
		earliest = 0;
		tmpProc = procList.at(h);
		tmpPair = pkb->getProcStartEnd(tmpProc);
		startLine = tmpPair.first;
		//printParentMatrix(*parentMatrix);
		updateParentMatrix(*parentMatrix, containerLines, startLine, containerEntity, earliest);
	}
	//printParentMatrix(*parentMatrix);
	pkb->setCommon(containerEntity, *parentMatrix);
}

void DesignExtractor::updateParentMatrix(Type::Map::ParentMatrix& parentMatrix, 
	Type::List::Line& containerLines, Type::Index::Line line, Type::Entity::Line containerEntity,
	Type::Index::Line  earliest){
		Type::Index::Line tmpLine;
		Type::List::Line followsLines = pkb->getFollowStar(line);
		unsigned int t, h;
		bool isIf, isWhile;

		for(t=0; t<followsLines.size()+1; t++){
			if(t<=0){
				tmpLine = line;
			}else{
				tmpLine = followsLines.at(t-1);
			}

			isIf = pkb->isLineEntity(tmpLine, Type::Entity::IF_LINE_ENTITY) ;
			isWhile = pkb->isLineEntity(tmpLine, Type::Entity::WHILE_LINE_ENTITY);

			// if the line is a container statement
			if(isIf || isWhile){
				// store another copy of the earliest parent passed in
				// and to be used in the child statements
				Type::Index::Line containerEarliest = earliest;
				updateParentMatrixOfContainer(parentMatrix, containerLines, tmpLine, 
					containerEntity, containerEarliest);

				// get first line(s) in container statement
				Type::List::Line containerChild;
				if(isIf){
					containerChild = pkb->getSuccessorNext(tmpLine);
				}else{
					Type::List::Line tmpList =pkb->getChild(tmpLine);
					containerChild.push_back(tmpList.front());
				}

				// recur on the container body
				for(h=0; h<containerChild.size(); h++){
					Type::Index::Line firstLineInChild = containerChild.at(h);

					updateParentMatrix(parentMatrix, containerLines, firstLineInChild, 
						containerEntity, containerEarliest);
				}
			}
		}
}

void DesignExtractor::updateParentMatrixOfContainer(Type::Map::ParentMatrix& parentMatrix, 
	Type::List::Line& containerLines, Type::Index::Line line, Type::Entity::Line entity,
	Type::Index::Line& earliest){
		Type::Index::Line rowLine, colLine;
		unsigned int k;

		// update column of line matrix for current container statment
		for(k=0; k<containerLines.size(); k++){
			rowLine = containerLines.at(k);

			Type::Map::ParentMap row;
			// container statement exists in column
			if(parentMatrix.find(rowLine) != parentMatrix.end()){
				// extract the row data of the column
				row = parentMatrix.at(rowLine);
				parentMatrix.erase(rowLine);
			}

			// get the procedure index of current container statement
			Type::Index::Proc procOfContainer = pkb->getProcIndexOfLine(line);
			Type::Pair::StartEnd startEnd = pkb->getProcStartEnd(procOfContainer);
			
			bool isRowEntity = pkb->isLineEntity(rowLine, entity);
			bool isRowParentStar = pkb->isParentStar(rowLine, line);
			Type::Index::Line earliestCommon = 0;

			// update earliest common only if current container statement and rowline
			// are in the same procedure 
			if(rowLine >= startEnd.first && rowLine <= startEnd.second){
				// if row ia a parent star of current line, 
				// it should be the earliest common parent and 
				// only if row has the same entity as the current line
				if(isRowParentStar && isRowEntity){
					earliestCommon = rowLine;
				} else {
					Type::Index::Line tmpParent = -1;
					bool isParentRowEntity;
					bool isParentStarRow;
					
					// recur on the parent star of current line to find out the common parent
					// between current line and row line
					Type::List::Line parents = pkb->getParentStar(line);
					for(unsigned int t=0; t<parents.size(); t++){
						tmpParent = parents.at(t);
						isParentRowEntity = pkb->isLineEntity(tmpParent, entity);
						isParentStarRow = pkb->isParentStar(tmpParent, rowLine);
	
						// if the parent is parent star of row line and
						// has the entity same as current line
						if (isParentStarRow && isParentRowEntity){
							earliestCommon = tmpParent;
							break;
						}
					}
				}
			}

			// update column of line matrix
			row.insert(std::make_pair<Type::Index::Line, Type::Index::Line>(line , earliestCommon));
			parentMatrix.insert(std::make_pair<Type::Index::Line, Type::Map::ParentMap>(rowLine, row));
		}

		// update row of line matrix for current container statment to other
		Type::Map::ParentMap row;
		for(k=0; k<containerLines.size(); k++){
			colLine = containerLines.at(k);

			// get the procedure index of current container statement
			Type::Index::Proc procOfContainer = pkb->getProcIndexOfLine(line);
			Type::Pair::StartEnd startEnd = pkb->getProcStartEnd(procOfContainer);

			bool isColEntity = pkb->isLineEntity(colLine, entity);
			bool isColParentStar = pkb->isParentStar(colLine, line);
			Type::Index::Line earliestCommon = 0;

			// update earliest common only if current container statment and colline
			// are in the same procedure 
			if(colLine >= startEnd.first && colLine <= startEnd.second){
				if(isColParentStar && isColEntity){
					earliestCommon = colLine;
				} else {
					Type::Index::Line tmpLine = line;
					Type::Index::Line tmpParent = -1;
					bool isParentColEntity;
					bool isParentStarCol;
					
					// recur on the parent star of current line to find out the common parent
					// between current line and col line
					Type::List::Line parents = pkb->getParentStar(tmpLine);
					for(unsigned int t=0; t<parents.size(); t++){
						tmpParent = parents.at(t);
						isParentColEntity = pkb->isLineEntity(tmpParent, entity);
						isParentStarCol = pkb->isParentStar(tmpParent, colLine);

						// if the parent is parent star of col line and has the entity same as current line
						if (isParentStarCol && isParentColEntity){
							earliestCommon = tmpParent;
							break;
						}
					}
				}
			}

			row.insert(std::pair<Type::Index::Line, Type::Index::Line>(colLine , earliestCommon));
		}

		// set current container statement to be the earliest common parent if it is while/if
		if(pkb->isLineEntity(line, entity)){
			earliest = line;
		}

		// update the last entry parentMatrix[line, line]
		row.insert(std::pair<Type::Index::Line, Type::Index::Line>(line , earliest));
		// update last row of line matrix
		parentMatrix.insert(std::pair<Type::Index::Line, Type::Map::ParentMap>(line, row));

		// add current line to container lines
		containerLines.push_back(line);
}

void DesignExtractor::printParentMatrix(Type::Map::ParentMatrix& parentMatrix){
	std::cout<<"\nPARENTMATRIX\n";
	// print line matrix
	Type::Map::ParentMatrix::iterator it;
	for(it = parentMatrix.begin(); it != parentMatrix.end(); it++){
		Type::Map::ParentMap row = it->second;

		if(it == parentMatrix.begin()){
			Type::Map::ParentMap::iterator itFirstRow;
			std::cout<<"\t";
			for(itFirstRow = row.begin(); itFirstRow != row.end(); itFirstRow++){
				std::cout<<itFirstRow->first<<"\t";
			}
			std::cout<<endl;
		}

		std::cout<<it->first<<"\t";

		Type::Map::ParentMap::iterator itRow;
		for(itRow = row.begin(); itRow != row.end(); itRow++){
			std::cout<<itRow->second<<"\t";
		}
		std::cout<<endl;
	}
}

void DesignExtractor::setExitPointsOfProcs() {
	Type::List::Proc procList = pkb->getProcIndices();
	for (auto procIter = procList.begin(); procIter != procList.end(); procIter++) {
		setExitPointOfProc(*procIter);
	}
}

void DesignExtractor::setExitPointOfProc(Type::Index::Proc proc) {
	assert (pkb->isProcExistInProcTable(proc));
	// Here, we are ensured that the proc exists

	// Start from the last line
	Type::Index::Line currentLine = pkb->getProcStartEnd(proc).second;
	// Find the highest-up while of the current line, and change currentLine to it
	while (true) {
		Type::Index::Line parent = pkb->getParent(currentLine);
		if (parent <= 0) {
			break;
		} else {
			Type::Index::Line whileLine = pkb->getCommon(Type::Entity::WHILE_LINE_ENTITY, parent, parent);
			if (whileLine > 0) {
				currentLine = whileLine;
			} else {
				break;
			}
		}
	}
	// Here, currentLine might be the last line of the procedure as before, 
	// or it might be the highest while line it is contained within
	// Either way, it is an exit point, so set it!
	// cout << "DE: setProcExitPoint(" << pkb->getProcName(proc) << ", " << currentLine << ")\n";
	pkb->setProcExitPoint(proc, currentLine);

	// But, we are not done.
	// As long as this line has IF ancestors (all the ancestors MUST be IFs due to above),
	// we will need to perform the same algorithm on the then stmtLst (because we MUST be currently in the else stmtLst)
	// of the parent.
	// Rinse and repeat on the parent of the parent's then stmtLst, until no more parents.
	Type::Index::Line parent = pkb->getParent(currentLine);
	while (parent > 0) {
		assert (pkb->isLineEntity(parent, Type::Entity::IF_LINE_ENTITY));
		
		currentLine = pkb->getLastOfIf(parent).at(0);
		// Find the highest-up while of the current line, and change currentLine to it
		while (true) {
			Type::Index::Line parent = pkb->getParent(currentLine);
			if (parent <= 0) {
				break;
			} else {
				Type::Index::Line whileLine = pkb->getCommon(Type::Entity::WHILE_LINE_ENTITY, parent, parent);
				if (whileLine > 0) {
					currentLine = whileLine;
				} else {
					break;
				}
			}
		}
		// Here, currentLine might be the last line of the procedure as before, 
		// or it might be the highest while line it is contained within
		// Either way, it is an exit point, so set it!
		// cout << "DE: setProcExitPoint(" << pkb->getProcName(proc) << ", " << currentLine << ")\n";
		pkb->setProcExitPoint(proc, currentLine);

		// Go up to the next parent
		parent = pkb->getParent(parent);
	}
}

int DesignExtractor::updateNextBipStatus_Yude(void) {
	/*--------------------------------------------------------------
	 *	NextBip is the same as Next,
	 *	except when:
	 *	1. the line is a CALL
	 *		- do not set next as nextBIP
	 *		- set first line of called proc as nextBIP
	 *	2. the line is an exit point
	 *		- additional nextBIPs, which is the exitToIndexes of the
	 *			proc which the line is in
	 *--------------------------------------------------------------*/
	Type::List::Line lineList = pkb->getLines();
	for (auto line = lineList.begin(); line != lineList.end(); line++) {
		Type::Entity::Line lineEntity = pkb->getLineEntityByLine(*line);
		Type::Index::Proc calledProc;
		Type::Index::Line firstLineOfCalledProc;
		switch (lineEntity) {
		case Type::Entity::CALL_LINE_ENTITY: 
			// call type, do not set next as nextBIP,
			// but instead set first line of called proc as nextBIP
			calledProc = pkb->getCalledByLine(*line);
			firstLineOfCalledProc = pkb->getProcStartEnd(calledProc).first;
			pkb->setNextBip(*line, firstLineOfCalledProc);
			break;
		default: // other cases nextBIP = next
			Type::List::Line nextList = pkb->getSuccessorNext(*line);
			for (unsigned int i = 0; i < nextList.size(); i++) {
				Type::Index::Line nextLine = nextList.at(i);
				pkb->setNextBip(*line, nextLine);
			}
			break;
		}
	}

	// Set all exit points to have additional nextBIPs (exitToIndexes)
	Type::List::Proc procList = pkb->getProcIndices();
	for (auto proc = procList.begin(); proc != procList.end(); proc++) {
		// For each proc, get its exit points and set the exitToIndexes 
		// of this proc as nextBIP
		Type::List::Line exitToIndexes = pkb->getProcExitToIndexes(*proc);
		Type::List::Line exitPoints = pkb->getProcExitPoints(*proc);
		for (auto exitPoint = exitPoints.begin(); exitPoint != exitPoints.end(); exitPoint++) {
			for (auto exitToIndex = exitToIndexes.begin(); exitToIndex != exitToIndexes.end(); exitToIndex++) {
				pkb->setNextBip(*exitPoint, *exitToIndex);
			}
		}
	}

	return 0;
}
